package com.wtgroup.demo.mianshi.算法.二叉树.遍历;

import cn.hutool.core.collection.CollUtil;
import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Tools;
import com.wtgroup.demo.mianshi.算法.二叉树.model.CompleteBinTree;
import com.wtgroup.demo.mianshi.算法.二叉树.model.Node;
import lombok.AllArgsConstructor;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/3/27 23:07
 */
public class D_中序 {

    public static void main(String[] args) {
        Judger.of(() -> {
            // List<Integer> vals = Arrays.asList(1,2,3,4,5,6,7,8);
            int[] ints = RandomUtil.randomArray(RandomUtil.randomInt(0, 1000), 0, 1000);
            List<Integer> vals = Arrays.asList(Tools.int2IntegerArray(ints));
            CompleteBinTree<Integer> binTree = new CompleteBinTree<Integer>(vals);
            // 8 4 2 5 1 6 3 7
            Node<Integer> root = binTree.getRoot();

            ArrayList<Node> res1 = new ArrayList<>();
            ArrayList<Node> res2 = new ArrayList<>();
            D_后序.m1(root, res1);
            // System.out.println();
            recurse_2_loop(root, res2);
            // System.out.println();
            return CollUtil.isEqualList(res1, res2);
        }).setIterCount(1000).start().print();
    }

    @AllArgsConstructor
    static class Frame {
        Node<Integer> node;
    }

    // 二叉树递归改迭代遍历
    static void recurse_2_loop(Node<Integer> head, ArrayList<Node> result) {
        /*
        首先, 递归, 想象成树的处理
        1. 入参看情况封装到 Frame 中, 用于压栈,出栈, 记录运行时信息. 一个节点处都会对应一个 Frame
        2. 递归的 base case 原样放到循环内部, 执行完 continue .
        3. 遇到递归调用处, 观察当前 Frame 压过栈的分支偏移量(任务提交过了,处理过了)  -- 具体场景可用灵活使用简单的判定方式
            3.1 达到分支个数, 说明, 所有子分支均已处理过, continue 下一轮迭代, 跳到 parent 处, 处理它的下一个子, 即我的后一个分支.
            3.2 否则, 自己压回栈中, 封装子节点处 Frame 压栈, 进入下一个子节点处处理.
        4. "自身" 处理, 原样放到循环内部对应位置.
         */
        // 异常数据处理
        if (head == null) {
            return;
        }

        Stack<Frame> stack = new Stack<>();
        stack.push(new Frame(head));
        Map<Frame, Integer> frameToOffsetMap = new HashMap<>();

        while (!stack.isEmpty()) {
            Frame currFrame = stack.pop();
            Node<Integer> node = currFrame.node;
            // 1. base case , continue -- 递归的退出条件
            // if xxx:
            //  continue
            if (node == null) {
                continue;
            }
            // --- ↑ continue -- 递归的退出条件 ---

            Integer currHandlePoint = frameToOffsetMap.getOrDefault(currFrame, -1) + 1;
            // 2. 择机调用处理器逻辑
            // 当前处理分支 和 指定调用的时机比较
            // if (currHandlePoint == (childCnt+1) / 2) {
            //     System.out.print(node.getData() + " ");
            // }

            // 3. 当前节点的子分支处理完了, continue
            // if frameOffsetMap.get(currFrame) == nexts.size
            //   continue

            // 如果左节点处理过了, 说明, 改处理我自身
            if (currHandlePoint == 2) {
                // System.out.print(node.getData() + " ");
                result.add(node);
            }

            if (currHandlePoint == 2) {
                continue;
            }


            // 4. 否则, 自己压回栈中, 封装子节点处 Frame 压栈, 进入下一个子节点处处理. 并更新当前节点的子分支偏移量
            stack.push(currFrame);
            stack.push(new Frame(currHandlePoint == 0 ? node.left : node.right));
            frameToOffsetMap.put(currFrame, currHandlePoint);
        }
    }

    private static int getChildCnt(Node<Integer> node) {
        int childCnt = 0;
        if (node.left != null && node.right != null) {
            childCnt = 2;
        } else if (node.left != null || node.right!= null) {
            childCnt = 1;
        }
        return childCnt;
    }


    /**
     * 递归
     * @param root
     */
    public static void m1(Node root, ArrayList<Node> result) {
        if (root != null) {
            m1(root.getLeft(), result);
            // System.out.print(root.getData() + " ");
            result.add(root);
            m1(root.getRight(), result);
        }
    }

    /**
     * 栈
     * <p>
     * '先序'逻辑为基础, 访问调到弹栈后
     */
    public static void m2(Node root) {
        Stack<Node> stack = new Stack<>();
        Node curNode = root;
        while (curNode !=null || !stack.isEmpty()) {
            if (curNode != null) {
                stack.push(curNode);
                curNode = curNode.getLeft();
            } else {
                Node p = stack.pop();
                System.out.print(p.getData() + " ");
                curNode = p.getRight();
            }
        }
    }

    static void m3(Node root) {
        /*
        m2 巧妙, 利用了叶子节点的两个null, 当弹出右null时, 自动弹出到了它的父, 从而顺利走到 right 分支.
        难想, 不够套路. 比如多叉呢? 不能走到第三叉.
        通用套路:
        压栈, 节点, 哪些叉处理过
        弹栈, 从未处理的叉开始, 压栈, 继续...
        关键是, 我得知道我的子的处理情况. 简单处理, 使用 set 记录那些节点处理过了.
         */
        Stack<Info> stack = new Stack<>();
        stack.push(new Info(root, 0));
        while (stack.isEmpty() == false) {
            Info info = stack.pop();
            Node curr = info.node;

            if (curr == null || info.handledNum == 2) {
                info.handledNum = 2;
                if (stack.isEmpty() == false) {
                    // 上报信息给父节点
                    stack.peek().handledNum++;
                }
                continue;
            };

            if (info.handledNum == 1) {
                // 处理我自己
                System.out.print(curr.getData() + " ");
            }

            Node[] children = new Node[]{curr.left, curr.right}; // 方便通用理解

            // for (int i = 0; i < children.length; i++) {
            //     Node child = children[i];
            //     if (info.handledNum == i) {
            //         stack.push(info);
            //         stack.push(new Info(child, 0));
            //         break;
            //     }
            // }

            Node child = children[info.handledNum];
            stack.push(info);
            stack.push(new Info(child, 0));
        }

    }

    @AllArgsConstructor
    static class Info {
        Node node;
        int handledNum;
    }



}
